package cn.leecode.q78;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 中等问题78: 子集
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
 * 子集
 * （幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * 示例 2：
 * 输入：nums = [0]
 * 输出：[[],[0]]
 * 提示：
 * 1 <= nums.length <= 10
 * -10 <= nums[i] <= 10
 * nums 中的所有元素 互不相同
 */
public class SubSet {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, nums, new ArrayList<>(), result);
        return result;
    }

    /**
     * 回溯算法
     *
     * @param start   开始索引
     * @param nums    需要遍历的数组
     * @param current 当前数组
     * @param result  结果数组
     */
    private void backtrack(int start, int[] nums, List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));
        for (int i = start; i < nums.length; i++) {
            // 添加元素到当前子集
            current.add(nums[i]);
            // 继续构建下一个元素
            backtrack(i + 1, nums, current, result);
            // 移除最后添加的元素，尝试其他组合
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        SubSet subSet = new SubSet();
        int[] nums = {1};
        List<List<Integer>> subsets = subSet.subsets(nums);
        System.out.println(subsets.toString());
//        // 打印结果
//        for (List<Integer> subset : subsets) {
//            System.out.println(subset);
//        }
    }
}
